Skip to content

Latest commit

 

History

History

0939-Minimum Area Rectangle

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
README_CN.md
README_CN.md
 
 
Sort.py
Sort.py
 
 
Sort.rs
Sort.rs
 
 

README.md

939. Minimum Area Rectangle

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] Output: 2

Note:

  1. 1 <= points.length <= 500
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. All points are distinct.

Solutions (Python)

1. Sort

classSolution: defminAreaRect(self, points: List[List[int]]) ->int: points_set=set() min_area=Nonepoints.sort() foriinrange(len(points)): x0, y0=points[i] forjinrange(i): x1, y1=points[j] if (x0, y1) inpoints_setand (x1, y0) inpoints_set: area= (x0-x1) *abs(y0-y1) min_area=areaifmin_areaisNone \ elsemin(min_area, area) points_set.add((x0, y0)) return0ifmin_areaisNoneelsemin_area

Solutions (Rust)

1. Sort

use std::collections::HashSet;implSolution{pubfnmin_area_rect(mutpoints:Vec<Vec<i32>>) -> i32{letmut set = HashSet::new();letmut min_area = None; points.sort_unstable();for i in0..points.len(){let(x0, y0) = (points[i][0], points[i][1]);for j in0..i {let(x1, y1) = (points[j][0], points[j][1]);if set.contains(&(x0, y1)) && set.contains(&(x1, y0)){let area = (x0 - x1)*(y0 - y1).abs(); min_area = Some(min_area.map_or(area, |a:i32| a.min(area)));}} set.insert((x0, y0));} min_area.unwrap_or(0)}}
close